package Draft;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class n_queens_debug {
    boolean[] CheckCol, CheckDig1, CheckDig2;
    char[][] path;
    int n;
    List<List<String>> ret;

    public  List<List<String>> solveNQueens(int _n) {
        n = _n;
        ret = new ArrayList<>();
        CheckCol = new boolean[n];
        CheckDig1 = new boolean[2 * n];
        CheckDig2 = new boolean[2 * n];
        path = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(path[i], '.');
        }
        dfs(0);
        return ret;
    }

    public void dfs(int row) {
        if (row == n) {
            List<String> tmp = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                tmp.add(new String(path[i]));
            }
            ret.add(new ArrayList<>(tmp));
            return;
        }

        for (int col = 0; col < n; col++) {
            if (CheckCol[col] == false && CheckDig1[row - col + n] == false && CheckDig2[row + col] == false) {
                path[row][col] = 'Q';
                CheckCol[col] = CheckDig1[row - col + n] = CheckDig2[row + col] = true;
                dfs(row + 1);
                // 恢复现场
                path[row][col] = '.';
                CheckCol[col] = CheckDig1[row - col + n] = CheckDig2[row + col] = false;
            }

        }
    }

    public static void main(String[] args) {
        n_queens_debug queen = new n_queens_debug();
        List<List<String>> list = new ArrayList<>();
        list = queen.solveNQueens(4);
    }
}
